import collections


# class Solution(object):
#     def numDistinctIslands2(self, grid):
#         """
#         :type grid: List[List[int]]
#         :rtype: int
#         """
#         m = len(grid)
#         n = len(grid[0])
#         total = set()
#         islands = collections.deque()
#         for i in range(m):
#             for j in range(n):
#                 if grid[i][j] == 1:
#                     islands.append({(i, j)})
#                     now_set = {(i, j)}
#                     while now_set:
#                         next_set = set()
#                         for x, y in now_set:
#                             for ux, uy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
#                                 if 0 <= ux < m and 0 <= uy < n and grid[ux][uy] == 1:
#                                     next_set.add((ux, uy))
#                                     grid[ux][uy] = 2
#                         now_set = next_set
#                         islands[-1].update(now_set)
#
#         def calculate(island):
#             new_island = {item[0] * n + item[1] for item in island}
#             min_value = min([item[0] for item in island]) * n + min(item[1] for item in island)
#             out_island = {item - min_value for item in new_island}
#             return out_island
#
#         def rotate0(island):
#             return island
#
#         def rotate1(island):
#             new_island = set()
#             node = island.pop()
#             new_island.add(node)
#             for item in island:
#                 new_island.add((node[0] - item[1] + node[1], node[1] + item[0] - node[0]))
#             island.add(node)
#             return new_island
#
#         def rotate2(island):
#             new_island = set()
#             node = island.pop()
#             new_island.add(node)
#             for item in island:
#                 new_island.add((2 * node[0] - item[0], 2 * node[1] - item[1]))
#             island.add(node)
#             return new_island
#
#         def rotate3(island):
#             new_island = set()
#             node = island.pop()
#             new_island.add(node)
#             for item in island:
#                 new_island.add((node[0] + item[1] - node[1], node[1] - item[0] + node[0]))
#             island.add(node)
#             return new_island
#
#         def fanzhuan(island):
#             new_island = set()
#             node = island.pop()
#             new_island.add(node)
#             for item in island:
#                 new_island.add((item[0], 2 * node[1] - item[1]))
#             island.add(node)
#             return new_island
#
#         def fanzhuan2(island):
#             new_island = set()
#             node = island.pop()
#             new_island.add(node)
#             for item in island:
#                 new_island.add((2 * node[0] - item[0], item[1]))
#             island.add(node)
#             return new_island
#
#         for island in islands:
#             island1 = tuple(calculate(island))
#             island2 = tuple(calculate(rotate1(island)))
#             island3 = tuple(calculate(rotate2(island)))
#             island4 = tuple(calculate(rotate3(island)))
#             island = fanzhuan(island)
#             island5 = tuple(calculate(rotate0(island)))
#             island6 = tuple(calculate(rotate1(island)))
#             island7 = tuple(calculate(rotate2(island)))
#             island8 = tuple(calculate(rotate3(island)))
#             island = fanzhuan2(island)
#             island9 = tuple(calculate(rotate0(island)))
#             island10 = tuple(calculate(rotate1(island)))
#             island11 = tuple(calculate(rotate2(island)))
#             island12 = tuple(calculate(rotate3(island)))
#             min_island = min(island1, island2, island3, island4, island5, island6, island7, island8, island9, island10,
#                              island11, island12)
#             total.add(min_island)
#         return len(total)

class Solution(object):
    def numDistinctIslands2(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = len(grid)
        n = len(grid[0])
        total = set()
        islands = collections.deque()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    islands.append({(i, j)})
                    now_set = {(i, j)}
                    while now_set:
                        next_set = set()
                        for x, y in now_set:
                            for ux, uy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                                if 0 <= ux < m and 0 <= uy < n and grid[ux][uy] == 1:
                                    next_set.add((ux, uy))
                                    grid[ux][uy] = 2
                        now_set = next_set
                        islands[-1].update(now_set)

        def calculate(island):
            # new_island = {item[0] * n + item[1] for item in island}
            x_min = min([item[0] for item in island])
            y_min = min(item[1] for item in island)
            out_island = [(item[0] - x_min, item[1] - y_min) for item in island]
            out_island.sort()
            return out_island

        def rotate0(island):
            return island

        def rotate1(island):
            new_island = {(-node[0], node[1]) for node in island}
            return new_island

        def rotate2(island):
            new_island = {(node[0], - node[1]) for node in island}
            return new_island

        def rotate3(island):
            new_island = {(-node[0], - node[1]) for node in island}
            return new_island

        def rotate4(island):
            new_island = {(node[1], node[0]) for node in island}
            return new_island

        def rotate5(island):
            new_island = {(node[1], - node[0]) for node in island}
            return new_island

        def rotate6(island):
            new_island = {(-node[1], node[0]) for node in island}
            return new_island

        def rotate7(island):
            new_island = {(-node[1], - node[0]) for node in island}
            return new_island

        for island in islands:
            island1 = tuple(calculate(island))
            island2 = tuple(calculate(rotate1(island)))
            island3 = tuple(calculate(rotate2(island)))
            island4 = tuple(calculate(rotate3(island)))
            island5 = tuple(calculate(rotate4(island)))
            island6 = tuple(calculate(rotate5(island)))
            island7 = tuple(calculate(rotate6(island)))
            island8 = tuple(calculate(rotate7(island)))
            min_island = min(island1, island2, island3, island4, island5, island6, island7, island8)
            total.add(min_island)
        return len(total)

data = Solution()
grid = [[1, 1, 1, 1], [1, 0, 1, 1], [0, 0, 0, 0], [0, 1, 1, 1], [1, 1, 0, 1]]
print(data.numDistinctIslands2(grid))
grid = [[1, 1, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 1], [0, 0, 0, 1, 1]]
print(data.numDistinctIslands2(grid))
grid = [[0, 1, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 1, 0]]
print(data.numDistinctIslands2(grid))
grid = [[1, 1, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 0, 1]]
print(data.numDistinctIslands2(grid))
grid = [[1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1], [1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0],
        [0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0], [1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0],
        [0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1], [1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0],
        [1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0], [0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1],
        [0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0], [1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1]]
print(data.numDistinctIslands2(grid))
